#include <iostream>
#include <vector>

using namespace std;
// 234. 回文链表
// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * Definition for singly-linked list.
*/
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
private:
    bool symmetry(vector<int> &a) {
        int i = 0, j = a.size() - 1;
        while(i < j) {
            if(a[i] != a[j]) return false;
            i++; j--;
        }
        return true;
    }
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr) return true;
        if(head->next == nullptr)   // 只有一个结点
            return true;
        if(head->next->next == nullptr) // 只有两个结点
            return head->val == head->next->val;

        vector<int> tmparr;
        ListNode* p = head;
        while(p != nullptr) {
            tmparr.push_back(p->val);
            p = p->next;
        }
        return symmetry(tmparr);
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
